package com.yanceysong.codetop.s31_s40;

public class S33_Mid_1143_最长公共子序列 {
    /**
     * 题目：S33_Mid_1143_最长公共子序列 (Longest Common Subsequence, LCS)
     * LeetCode: <a href="https://leetcode.cn/problems/longest-common-subsequence/">...</a>
     * ----------------------------------------------
     * 给定两个字符串 text1 和 text2，返回它们的 最长公共子序列 的长度；如果不存在公共子序列，返回 0。
     * “子序列”指可以通过删除原字符串中的某些字符（或不删），且不改变剩余字符相对顺序得到的新字符串。
     * 示例："ace" 是 "abcde" 的子序列；但 "aec" 不是 "abcde" 的子序列（顺序被破坏）。
     * ----------------------------------------------
     * 示例：
     * 1) 输入：text1 = "abcde", text2 = "ace"  输出：3   解释：LCS = "ace"
     * 2) 输入：text1 = "abc",   text2 = "abc"  输出：3   解释：LCS = "abc"
     * 3) 输入：text1 = "abc",   text2 = "def"  输出：0   解释：没有公共子序列
     * ----------------------------------------------
     * 核心思路（经典二维动态规划）：
     * 定义：lengthTable[i][j] 表示 text1 前 i 个字符 与 text2 前 j 个字符 的 LCS 长度。
     * 递推：
     * .   若 text1[i-1] == text2[j-1]，则这一对字符可以作为 LCS 的尾部之一：
     * .      lengthTable[i][j] = lengthTable[i-1][j-1] + 1
     * .  否则，当前两个尾字符不同，只能抛弃其中一个尾部去尝试：
     * .      lengthTable[i][j] = max(lengthTable[i-1][j], lengthTable[i][j-1])
     * 边界：当 i == 0 或 j == 0 时，任一字符串前缀为空，公共子序列长度为 0，初始化数组默认为0即可。
     * 答案：lengthTable[len1][len2]
     * ----------------------------------------------
     * ASCII 图解（示例：text1 = "abcde"，text2 = "ace"）：
     * 令行对应 text1 前缀长度 i，列对应 text2 前缀长度 j。
     * 行列 0 代表空串前缀，占位使公式统一。
     * <p>
     * .        j→   0  1(A) 2(C) 3(E)
     * .i↓   +----------------------
     * .0( ) |  0   0    0    0
     * .1(A) |  0   1    1    1
     * .2(B) |  0   1    1    1
     * .3(C) |  0   1    2    2
     * .4(D) |  0   1    2    2
     * .5(E) |  0   1    2    3   ← 最终答案 3
     * <p>
     * 解释：
     * - A匹配 → 第一行第二列取 0+1 = 1
     * - B 不匹配 → 取 max(上一行, 左一列) = 1
     * - C 匹配 → 在 (3,2) 位置由 (2,1)+1 = 2
     * - E 匹配 → 在 (5,3) 位置由 (4,2)+1 = 3
     * ----------------------------------------------
     * 可选优化：空间压缩到一维 O(min(len1,len2))（不在此主实现中，保持易读性）。
     * 时间复杂度：O(len1 * len2)
     * 空间复杂度：O(len1 * len2)
     */
    public int longestCommonSubsequence(String text1, String text2) {
        // len1/len2 表示两个字符串长度
        int len1 = text1.length();
        int len2 = text2.length();
        // lengthTable[i][j] 含义：text1前i个字符 与 text2前j个字符 的LCS长度
        int[][] lengthTable = new int[len1 + 1][len2 + 1];

        // 外层遍历 text1 前缀长度 i
        for (int i = 1; i <= len1; i++) {
            char ch1 = text1.charAt(i - 1);  // 当前考虑的 text1 第 i 个字符（下标 i-1）
            // 内层遍历 text2 前缀长度 j
            for (int j = 1; j <= len2; j++) {
                char ch2 = text2.charAt(j - 1);  // 当前考虑的 text2 第 j 个字符（下标 j-1）
                if (ch1 == ch2) {
                    // 两个尾字符相等：可以作为公共子序列的尾部，继承左上方结果 +1
                    lengthTable[i][j] = lengthTable[i - 1][j - 1] + 1;
                } else {
                    // 不相等：不能同时使用，分别尝试“去掉 text1 的当前尾”或“去掉 text2 的当前尾”
                    lengthTable[i][j] = Math.max(lengthTable[i - 1][j], lengthTable[i][j - 1]);
                }
            }
        }
        return lengthTable[len1][len2];
    }

    // ---------------------------------- 测试主程序 ----------------------------------
    public static void main(String[] args) {
        S33_Mid_1143_最长公共子序列 solution = new S33_Mid_1143_最长公共子序列();
        System.out.println("=== 最长公共子序列 LCS 测试开始 ===\n");

        testBasicExample(solution);         // 示例1
        testIdenticalStrings(solution);     // 完全相同
        testNoCommonSubsequence(solution);  // 没有公共子序列
        testWithEmptyString(solution);      // 含空串
        testRepeatedCharacters(solution);   // 重复字符场景
        testClassicCase(solution);          // 经典教材案例
        testUnicodeCase(solution);          // Unicode / 中文测试

        System.out.println("\n=== 所有测试完成 ===");
    }

    // 测试1：题目示例
    private static void testBasicExample(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试1: 基本示例 ---");
        String a = "abcde", b = "ace";
        int ans = s.longestCommonSubsequence(a, b);
        System.out.println("输入: a=" + a + ", b=" + b);
        System.out.println("输出: " + ans + " (期望: 3)");
        assert ans == 3 : "LCS 应为 3";
        System.out.println("✓ 通过\n");
    }

    // 测试2：完全相同
    private static void testIdenticalStrings(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试2: 完全相同字符串 ---");
        String a = "abc", b = "abc";
        int ans = s.longestCommonSubsequence(a, b);
        System.out.println("输入: a=" + a + ", b=" + b);
        System.out.println("输出: " + ans + " (期望: 3)");
        assert ans == 3 : "LCS 应为 3";
        System.out.println("✓ 通过\n");
    }

    // 测试3：无公共子序列
    private static void testNoCommonSubsequence(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试3: 无公共子序列 ---");
        String a = "abc", b = "def";
        int ans = s.longestCommonSubsequence(a, b);
        System.out.println("输入: a=" + a + ", b=" + b);
        System.out.println("输出: " + ans + " (期望: 0)");
        assert ans == 0 : "LCS 应为 0";
        System.out.println("✓ 通过\n");
    }

    // 测试4：含空串
    private static void testWithEmptyString(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试4: 含空字符串 ---");
        String a = "", b = "abc";
        int ans1 = s.longestCommonSubsequence(a, b);
        int ans2 = s.longestCommonSubsequence(b, a);
        System.out.println("输入: a=\"\", b=" + b + " -> 输出: " + ans1 + " (期望: 0)");
        System.out.println("输入: a=" + b + ", b=\"\" -> 输出: " + ans2 + " (期望: 0)");
        assert ans1 == 0 && ans2 == 0 : "空串与任意串 LCS 应为 0";
        System.out.println("✓ 通过\n");
    }

    // 测试5：重复字符（容易误以为要去重）
    private static void testRepeatedCharacters(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试5: 重复字符场景 ---");
        String a = "aaaaa", b = "aaa"; // 任意三个 'a' 就能组成公共子序列
        int ans = s.longestCommonSubsequence(a, b);
        System.out.println("输入: a=" + a + ", b=" + b);
        System.out.println("输出: " + ans + " (期望: 3)");
        assert ans == 3 : "LCS 应为 3";
        System.out.println("✓ 通过\n");
    }

    // 测试6：经典案例（教材常见）
    private static void testClassicCase(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试6: 经典案例 ---");
        String a = "AGGTAB", b = "GXTXAYB"; // LCS = GTAB 长度 4
        int ans = s.longestCommonSubsequence(a, b);
        System.out.println("输入: a=" + a + ", b=" + b);
        System.out.println("输出: " + ans + " (期望: 4)");
        assert ans == 4 : "LCS 应为 4 (GTAB)";
        System.out.println("✓ 通过\n");
    }

    // 测试7：Unicode / 中文字符
    private static void testUnicodeCase(S33_Mid_1143_最长公共子序列 s) {
        System.out.println("--- 测试7: Unicode / 中文 ---");
        String a = "你好世界", b = "世你好"; // 可能的公共子序列："你好" / "世好" / "你世" 等，最长长度 2
        int ans = s.longestCommonSubsequence(a, b);
        System.out.println("输入: a=" + a + ", b=" + b);
        System.out.println("输出: " + ans + " (期望: 2)");
        assert ans == 2 : "LCS 应为 2";
        System.out.println("✓ 通过\n");
    }
}
